COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00020 00003	Notes:
C00029 00004	Results of coloring the map of the U.S.
C00033 ENDMK
C⊗;

                   COLORING MAPS AND THE KOWALSKI DOCTRINE
    
Kowalski (l97 ) enunciated the doctrine expressed by the formula

         program = logic + control

	The formula isn't precise, and won't be precise until Kowalski or
someone else proposes a precise and generally accepted notion of how
control is to be added to an expression of the logic of a program.
Nevertheless, I, for one, like the idea and believe it can be made to work
for some interesting class of programs.  It is analogous to my comparison
of epistemology and heuristics or Chomsky's competence and performance.

	Pereira and Porto (1981) give a logic program for coloring planar
maps with four colors and discuss how their notion of "intelligent
backtracking" can reduce the search involved in coloring a map from that
done by a straightforward PROLOG execution of the same
program.

	The discussion by Pereira and Porto treats coloring maps purely as
an example of logic programming, and the improvements they discuss apply
to all logic program systems.  We shall consider two mathematical ideas
about map coloring that go back to Kempe (1879), the paper containing the
original false proof of the four color theorem.  While Kempe's proof
was false, the ideas are good and were used in almost all subsequent work
including the successful proof ( ).

	Our question is whether an algorithm
A involving these ideas can be regarded as a form of control adjoined to
the basic logic program or whether they necessarily involve a new program.
If they are to be regarded as control structures, we do not yet know how
they are to be expressed.  Of course, it is not hard to write a completely
new program in PROLOG or any other language expressing algorithm A, but
perhaps it can be regarded as control attached to the Pereira-Porto logic.

	2.  The Pereira-Porto logic program

	There are two parts.  The first expresses that the adjacent
countries must have different colors by listing the pairs of colors that
may be adjacent.  We have

(1)	next(yellow,blue)← next(yellow,red), next(yellow,green),
next(blue,yellow), etc.

	The remaining PROLOG statement is distinct for each map.  For the
map of Figure 1, which they use as an example,




	Figure 1


it is

(2)	goal(R1,R2,R3,R4,R5,R6) ← next(R1,R2),next(R1,R3),next(R1,R5),
next(R1,R6),next(R2,R3),next(R2,R4),next(R2,R5),next(R2,R6),next(R3,R4),
next(R3,R6),next(R5,R6).

where each literal expresses the fact that a particular pair of adjacent
regions must be compatibly colored.

	Pereira and Porto give a trace of the execution of the program by
standard depth first PROLOG.  They point out that when an attempt to
satisfy a literal fails, because the two adjacent regions mentioned have
been assigned the same color, standard PROLOG will take back
the most recent assignment of a color even if the region most recently
colored was neither of those involved in the incompatibility.  Their
intelligent backtracking will change the color of one of the regions
giving the incompatibility.

	An outsider to logic programming may react unsympathetically and
comment that this is just one more example of a logic programming system,
with its standard way of doing searches, tripping over its own feet.
However, we should also recall that brief and easy statement of the PROLOG
program for the coloring and not give up this virtue without a fight.
However, the Pereira and Porto
"intelligent backtracking" doesn't make (1) and (2) into a good coloring
program.  Indeed we shall argue that it doesn't even do full justice to the
logic of the program.  To see this we need two ideas of Kempe.

	3.  Reducing the map

	Kempe noticed that countries with three or fewer neighbors present
no problem.  No matter how the rest of the map is colored, there is always
a color available for such a country.  This suggests "reducing the map" by
removing such countries and doing our trial-and-error coloring on the
reduced map, confident that once the reduced map is colored, the coloring
can be extended to the omitted countries.

	The idea is even more powerful because eliminating countries with
three or fewer neighbors may remove enough neighbors from some other
countries so that they have three or fewer neighbors and can themselves be
removed.  Therefore, the reduction process should be continued until a
reduced map is obtained in which all countries have at least four
neighbors.
  The maps of the states of the U.S. and
the countries of Europe, Asia, Africa and South America all reduce
to null maps when countries with three or fewer neighbors are successively
eliminated

	In the example of Figure 1 the reduced map is empty.  
Thus we may remove country 4 with two neighbors leaving country 3 with only
three neighbors, etc.  The successive removals 4,3,2,1,5,6, leave an empty
reduced map.  Therefore, when we colored in the reverse order
6,5,l,2,3,4, each country is colored without changing the
color of any previously colored country.

	If the programmer performs this reduction before he writes the
goal statement, he will write

	goal(R1,R2,R3,R4,R5,R6) ← next(R5,R6),next(R1,R5),next(R1,R6),
next(R1,R2),next(R2,R5),next(R2,R6),next(R1,R3),next(R2,R3),next(R3,R6),
next(R2,R4),next(R3,R4).

	This PROLOG program will run with only the most local
backtracking.  Namely, after R6 has been chosen arbitrarily, several
values will have to be tried for each of the variables R5,R1,R2,R3,R4, but
once a value has been found that is compatible with the previously
determined variables, it won't have to be changed again.

	The new PROLOG program is logically equivalent to the previous
program because it is just a rearrangement of the literals of a
conjunction.  However, the programmer has done the control.  The
interesting question is whether the reduction can be expressed in some way
that can be regarded as adding control to the original logic, i.e.,
without changing the original logic.

	4.  Kempe transformations

	Another idea of Kempe's can be used to strengthen the reduction
process, but regarding it as mere control added to the original logic program
seems even harder.

	The strengthened reduction procedure also removes countries with
four neighbors so that the reduced map contains only countries with five
or more neighbors.  The validity of this reduction depends on the following
Kempe proof
that if we have colored a partial map and want to add a country
with four neighbors, we can always revise the coloring of the partial map
to permit coloring the four neighbor country.

	If fewer than four colors have been used to color the neighbors,
there is no problem, so suppose that the four neighbors have been colored
with four different colors as shown in Figure 2.



	Figure 2



	Consider the set of all countries that can be reached from the
blue country A on top of Figure 2 by a path going through only blue and
yellow countries.  This set is called the blue-yellow Kempe component of
country A.  There are two cases.  Either it contains country C or not.  If
not, we recolor the partial map by reversing blue and yellow on all
countries in the blue-yellow Kempe component of A.  This still leaves the
partial map properly colored.
  The reader may take this as obvious after
looking at examples or he may consult the proof in ( ).
  Since the
blue-yellow Kempe component of A does not contain C, it remains yellow
while A has become yellow.  This makes blue available to extend the
coloring to X.

	In the other case, the blue-yellow Kempe component of A contains
C, i.e, there is a chain of adjacent countries from A to C each of which
is colored blue or yellow.  Then there cannot be a red-green chain from B
to D (by the Jordan curve theorem), so that a red-green Kempe
transformation applied to the red-green Kempe component of B will make B
green, leaving red available to color X.

	The fact that a blue-yellow path from A to C blocks a red-green
path from B to D is where we have used the fact that the map is on a plane
or sphere.

	This justifies eliminating countries with four neighbors in the
reduction process.  If we have colored a partial map and want to add a
country with four neighbors, we can do so, but we may have to modify the
previous coloring by means of a Kempe transformation.

	Our improved coloring algorithm then reduces the map by repeatedly
dropping countries with four or fewer neighbors, colors the reduced map
exhaustively, and then colors the dropped countries in the reverse order
using Kempe transformations when necessary.

	We can regard coloring the dropped countries as a process of
satisfying the goal of (2), using a very specific process of revising the
values of variables.  Whenever a Kempe transformation is made, all the
variables corresponding to countries in a Kempe component have their
values changed simultaneously in a specific way.  A very powerful means of
specifying control will be required.

	The Pereira-Porto selective backtracking is still required for
coloring reduced maps.  It will also do the right thing when the map is
divided into continents with no connections between countries in different
continents.  Even if the adjacencies are listed in a mixed order among
continents, it won't try to cure a problem in coloring one continent by
changing the color of another.  Also the reduction algorithms will work
ok in the multi-continent case.  However, we can still imagine some use
for a control algorithm that would first divide the map into connected
subsets.

	Another interesting case occurs when the map is divided into
two parts A and B by a ring C of three countries.  If we color A∪C and
B∪C separately, we can combine the colorings to get a coloring of the
whole map, but we may have to permute the colors on one component in
order to color C consistently.  Some of the research on the four color
theorem involved classifying colorings of larger rings.

	The coloring algorithms implicit in
( ) will involve a much more complex control process.  Other algorithms
for satisfying systems of constraints can also be studied as control added
to logic.

	To summarize, coloring maps may involve at least 5 kinds of control
applied to the original logic.

	1. Pereira-Porto selective backtracking.

	2. Kowalski-Bowen selection of a next goal.

	3. Postponement of postponable variables.  This may be done in
by virtue of a general theorem, i.e. that countries with three or fewer
neigbors are postponable or by an ad hoc theorem for a particular variable.

	4. Algorithms like Kempe transformations that revise previously
determined variables in problem dependent ways.

	5. Division of the problem into subproblems which can be solved
either independently or successively.
Notes:

1. The Pereira-Porto program has too limited an ontology to admit much
control to its ontology.  Maps, partial colorings of maps, and even
countries are not objects.  Heuristics may require additional objects
such as reduced maps and ordered lists of countries.

2. Program fragments

ok(y,b).
ok(b,y).
...

adj(r1,r2).
adj(r1,r3).
...

color(Map,X) :- reduce(Map,Y),color1(Y,Z),finish(Z,X).

colored(r1,R1) or colored(r1,R1,Partialmap)

goal(R1,...,R6) :- (putoff(r1);putoff(r2);ok(R1,R2));

Jul 13

3. In setting up the logic of the program, there is no need to be restricted
to clausal form.  Let's do an unprejudiced set theory axiomatization and
then see about expressing an algorithm in Horn clause form.
With the set theory we can construct heuristic entities like
coloring sequences as well as purely epistemological entities.
Perhaps Lisp or Prolog programs can also be entities.
Most likely literals, clauses, and sets of clauses with the same
head predicate symbols will have to be entities.

See color.ax[e81,jmc]

See maps.pr[e81,jmc]

4. There is a general method of achieving prolog goals which says that
some subgoals can be delayed because they can be achieved however the
others are achieved, while their achievement may interfere with the
achievement of the others.  Is this "method of postponable goals" usable
for other problems than coloring?

5. We must consider postponable goals and p. variables.  It seems that
one might often be able to prove a theorem to the effect that a certain
set of goals can be achieved with the freedom to determine the values
of variables x,...,z no matter what values are assigned to the other
variables.  If these are all the goals in which x,...,z appear, then
the goals and variables can be postponed.

6. It seems we can generalize Kempe transformations.  A set of variables
and the goals containing them may admit a group of transformations
that preserve the truth values of the goals.  The problem of assigning
professors and rooms to courses will admit such groups of transformations.
It is important to note that as with map coloring, the group of transformations
will in general depend on the decisions already made.

7. Postponing coloring countries with three or fewer neighbors is
legitimized by proving

	∀x y z ∃w.(n(x,w) ∧ n(y,w) ∧ n(z,w))

which is generally true where n(x,y) stands for what Pereira and Porto
call next(x,y).  Here we have a single relation which permits
postponing all countries with three or fewer neighbors.  In a less
homogeneous problem, we would expect that a postponable variable
in a body would have a special relation that could be proved in
order to postpone it.  Looking for postponable variables is obviously
expensive, so it must be under the user's control or the control of
some higher level program that knows that not seeking postponable
variables will lead to much backtracking.

	If we imagine (1) to be proved by first order logic using the ontology
of colors or even regions,
the proof may involve checking all 4↑3 = 64 combinations of x, y and z
and finding the required w.  The counting argument that if there are only
three of x, y, and z, then there is a fourth color for w requires a higher
level ontology.  Namely we must be able to argue about the cardinality of
sets of colors.
  However, this is a somewhat special case because of the
mutual similarity of the goals in a coloring problem.  In other cases,
the given ontology may permit reasonable proofs of the postponability
theorems, or at least there may be no advantage in going to a higher
level.

8. We suggest adding to Prolog a construction of the form

	reorderable(p1,...,pn)

Its meaning is logically the same as that of the list of literals (p1,...,pn),
but Prolog is allowed to reorder it by doing postponements and
immediacies.  Maybe we also need more specific re-orderings such as

	reorder(A,p1,...,pn)

where A is a rule for re-ordering.  We could allow meta rules or macros,
where

	macro(A([p1,...,pn],Macro-expansion))

applies the macro A to the clauses to get a macro-expansion which is
actually run.  Those macros that are merely re-orderings, i.e. change
the control but not the logic, seem to merit preferential treatment.

Aug 17

	In common sense reasoning, postponable variables are very
common, but their treatment is much more subtle than is required
by coloring problems.

Example: In planning a trip one ordinarily postpones deciding how to get to the
airport until after deciding what flight to take.  This is justified
by the fact that the decision about what flight to take is made on
criteria that do not include going to the airport.  On the other hand,
deciding on the flight determines how to go.  Notice that the postponability
of deciding how to go to the airport is an ad hoc decision and not
based on a general criterion like the variable appearing in only three
literals.

	Actually, the ways of getting to the airport can affect the
chosen flight.  One may decide to take the same flight as another
person in order to share transportation.  However, this is usually
a secondary consideration in the sense that it is used in a second
iteration of a plan.

(doctrine: Horn clauses and depth first search are in general the right
way to solve problems at the basic level.  Non-Horn clauses and other
kinds of search are done after some reification - at least reification
of tactics.  Hmm!  This seems to be in some contradiction to the
Kowalski doctrine).
Results of coloring the map of the U.S.

| ?- cs(X).

X = [[ca|y],[az|b],[nev|g],[oreg|r],[wash|y],[ida|b],[ut|y],[mont|y],[wyo|r],[nm
|r],[colo|b],[tex|b],[ndak|r],[minn|y],[sdak|b],[la|y],[miss|g],[ark|r],[okla|y]
,[kans|r],[neb|y],[io|r],[mo|b],[ala|b],[fla|y],[scar|y],[ga|r],[ncar|b],[tenn|y
],[dc|b],[va|g],[wisc|b],[ill|y],[mich|r],[ind|b],[kent|r],[ohio|y],[wva|b],[md|
y],[del|b],[penn|r],[nj|y],[conn|g],[ny|b],[ri|y],[mass|r],[nh|b],[me|y],[vt|y]]

  23:22:10 PROLOG IO wait at 700271  Used 0:02:10.8 in 0:41:22, Load   0.74

248. pages, Entry vector loc 0 len 254000

0-233	 Private   R, W, E
367-400	 Private   R, W, E
401-466	 MRC:<PROLOG>PROLOG.EXE.1  7-74   R, CW, E
700-731	 <SUBSYS>PA1050.EXE.5  1-32   R, CW, E
732-733	 Private   R, W, E